package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/">添加与搜索单词 - 数据结构设计(Design Add and Search Words Data Structure)</a>
 * <p>请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。</p>
 * <p>实现词典类 WordDictionary ：
 * <ul>
 *     <li>WordDictionary() 初始化词典对象</li>
 *     <li>void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配</li>
 *     <li>bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。</li>
 * </ul>
 * </p>
 * <p>
 *     <b>示例：</b>
 * <pre>
 *      输入：
 *          ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
 *          [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
 *      输出：
 *          [null,null,null,null,false,true,true,true]
 *
 *      解释：
 *          WordDictionary wordDictionary = new WordDictionary();
 *          wordDictionary.addWord("bad");
 *          wordDictionary.addWord("dad");
 *          wordDictionary.addWord("mad");
 *          wordDictionary.search("pad"); // 返回 False
 *          wordDictionary.search("bad"); // 返回 True
 *          wordDictionary.search(".ad"); // 返回 True
 *          wordDictionary.search("b.."); // 返回 True
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>1 <= word.length <= 25</li>
 * <li>addWord 中的 word 由小写英文字母组成</li>
 * <li>search 中的 word 由 '.' 或小写英文字母组成</li>
 * <li>最多调用 10^4 次 addWord 和 search</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/19 10:59
 */
public class _LC0211DesignAddAndSearchWordsDataStructure_M {
    static class WordDictionary {

        private WordDictionary[] children;
        private boolean isEnd;

        public WordDictionary() {
            children = new WordDictionary[26];
            isEnd = false;
        }

        public void addWord(String word) {
            WordDictionary curr = this;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (curr.children[index] == null) {
                    curr.children[index] = new WordDictionary();
                }
                curr = curr.children[index];
            }
            curr.isEnd = true;
        }

        public boolean search(String word) {
            return false;
        }

    }

    public static void main(String[] args) {
        WordDictionary wordDictionary = new WordDictionary();
        wordDictionary.addWord("bad");
        wordDictionary.addWord("dad");
        wordDictionary.addWord("mad");
        //System.out.println(wordDictionary.search("pad"));
        //System.out.println(wordDictionary.search("bad"));
        //System.out.println(wordDictionary.search(".ad"));
        System.out.println(wordDictionary.search("b.."));
    }
}
